阅前说明:
单源最短路与多源最短路:
单源最短路:求从一个固定起点出发,到图中任意顶点的最短距离.
多元最短路:求从任意起点出发,到图中任意顶点的最短路距离.
*当然,求单源最短路的算法重复执行n次(n是总顶点个数)就是多源最短路算法.而多源最短路算法在无时间限制的情况下,也可以用作单源最短路算法
松弛: 最短路的核心思想.
操作方式:以某一个顶点作为中转站,更新与这个顶点相邻的其他顶点的数值
(这种操作称为对中转站顶点的松弛)
(上述说法选自Yuilice老师的最短路算法,这里会配图更详细的解释这个说法)
比如这张无向图(标明的数字是路径长度):
现已知想要从点A走到点D有一条路:A -> C -> D (路径长度:25)
那现在取点B作为中转站进行松弛,发现:
A -> B ->D 这条路径长度为22.
那么就将点A到点D的最短距离更新为22
一.Dijkstra
最短路算法的一种,单源最短路算法,基于贪心思想.但同样,其缺点也因贪心思想而诞生.
其主要过程:不断挑选与起始点距离最近的点,并利用挑选到的点与其他顶点进行松弛.(每个点只会被挑选一次)
贪心思想的体现:挑选与起始点"距离最近的点"
贪心思想带来的缺点:无法处理负权便
可以使用堆优化时间复杂度:在挑选与起点距离最近的点时,利用优先队列"priority_queue"
时间复杂度:
O(mlogn)\textstyle O(m \log n) O(mlogn)
例题:P4779 【模板】单源最短路径（标准版)
代码:
二.SPFA
最短路算法的一种,单源最短路算法,铃铛人的优化.与DIJ不同,SPFA的松弛从边入手,将每次产生了变化的边的点放入队列.
也因此,SPFA与DIJ不同,它可以解决负权边,也可以判断负环.
优化:相比于Bellman,SPFA不会对没有发生变化的边进行无意义的松弛(取自Yuilice老师的最短路算法
判断负环:SPFA中,一个点不会被加入队列超过(>=)n次.
例题:T18691.小码君的太空基地【SPFA】
补充:注意到SPFA和Dijkstra都有一个叫vis的数组(从个人角度来说,我认为SPFA和Dijkstra的代码长得还是挺像的,所以要注意区分.)不同点在于,SPFA的vis[i]代表的是i这个顶点是否在队列中;而Dijkstra的vis[i]代表的是i这个顶点有没有松弛过.
三.Floyd
最短路算法的一种,相对于SPFA和Dijkstra来说,是多源最短路算法.和动态规划有异曲同工之妙.
优点在于代码简单易写易理解.缺点在于时间复杂度高达O(n3)O(n^3)O(n3)
操作方式:三层循环,第一层循环枚举松弛顶点,第二层循环枚举起点,第三层循环枚举终点.
例题:A29680.最短距离查询【Floyd】
智慧代码:
*本篇学习讨论部分内容基于Yuilice老师的最短路算法 嗷嗷嗷嗷嗷窝最短路算法梦开始的地方,预习的时候就逮着这篇疯狂学 感谢老师
并且感谢 BaiRX 同学提出的 这篇学习讨论的漏洞 万分感谢!(●'◡'●)
